package leetCode.q105;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Me {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder){
        int len = preorder.length;
        if(len == 0) return null;
        if(len == 1) return new TreeNode(preorder[0]);

        List<Integer> pre = Arrays.stream(preorder).boxed().collect(Collectors.toList());
        List<Integer> in = Arrays.stream(inorder).boxed().collect(Collectors.toList());

        TreeNode root = new TreeNode(preorder[0]);

        int mid = in.indexOf(preorder[0]);
        if(mid == -1){
            System.out.println(1);
        }
        List<Integer> leftIn = in.subList(0,mid);
        List<Integer> rightIn = in.subList(mid+1,in.size());
        List<Integer> leftPre = new ArrayList<>();
        List<Integer> rightPre = new ArrayList<>();
        if(mid == 0){
            //没有左子树
            rightPre = pre.subList(1,len);
        } else if (mid == len-1) {
            //没有右子树
            leftPre = pre.subList(1,len);
        }else {
            leftPre = pre.subList(1,pre.indexOf(inorder[mid-1])+1);
            rightPre = pre.subList(pre.indexOf(inorder[mid-1])+1,len);
        }

        root.left = buildTree(leftPre.stream().mapToInt(Integer::intValue).toArray(),leftIn.stream().mapToInt(Integer::intValue).toArray());
        root.right = buildTree(rightPre.stream().mapToInt(Integer::intValue).toArray(),rightIn.stream().mapToInt(Integer::intValue).toArray());

        return root;
    }

    public static void main(String[] args) {
        new Me().buildTree(new int[]{3,2,1,4},new int[]{1,2,3,4});
    }
}
